package com.ting.test.algorithms.Moris;

import com.ting.test.algorithms.二叉树.TreeNode;
import com.ting.test.algorithms.链表.SingleNode;

/**
 * 利用moris算法 遍历二叉树
 * 思路
 * 假设来到当前节点cur，开始时cur来到头节点位置
 * 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
 * <p>
 * 2）如果cur有左孩子，找到左子树上最右的节点mostRight：
 * <p>
 * a.如果mostRight的右指针指向空，让其指向cur，	然后cur向左移动(cur = cur.left)
 * <p>
 * ​       b.如果mostRight的右指针指向cur，让其指向null，	然后cur向右移动(cur = cur.right)
 * <p>
 * 3）cur为空时遍历停止
 */
public class 定义 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        process(head);
    }

    private static void process(TreeNode head) {
        TreeNode current = head;
        while (current != null) {
            if (current.getLeft() != null) {
                //找到current的左子树上的最右节点
                TreeNode mostRight = current.getLeft();
                while (mostRight.getRight() != null && mostRight.getRight() != current) {
                    mostRight = mostRight.getRight();
                }
                //如果current的左子树的最右节点的右指针为空.将其指向当前节点
                if (mostRight.getRight() == null) {
                    mostRight.setRight(current);
                    current = current.getLeft();
                    continue;
                } else {
                    // 如果当前节点的左子树的最右节点的右指针指向current 表明这是第二次来到current了，
                    mostRight.setRight(null);
                }

            }
            current = current.getRight();
        }

    }

    /**
     * 先序遍历
     *
     * @param head
     */

    private static void processPre(TreeNode head) {
        TreeNode current = head;
        while (current != null) {
            if (current.getLeft() != null) {
                //找到current的左子树上的最右节点
                TreeNode mostRight = current.getLeft();
                while (mostRight.getRight() != null && mostRight.getRight() != current) {
                    mostRight = mostRight.getRight();
                }
                //如果current的左子树的最右节点的右指针为空.将其指向当前节点
                if (mostRight.getRight() == null) {
                    mostRight.setRight(current);
                    System.out.printf(current.getVal() + "");//先序遍历  第一次来到该节点
                    current = current.getLeft();
                    continue;
                } else {
                    // 如果当前节点的左子树的最右节点的右指针指向current 表明这是第二次来到current了，
                    mostRight.setRight(null);
                }
            }
            System.out.printf(current.getVal() + "");//先序遍历 考虑左子树为空的情况
            current = current.getRight();
        }

    }


    /**
     * 中序遍历
     *
     * @param head
     */

    private static void processMid(TreeNode head) {
        TreeNode current = head;
        while (current != null) {
            if (current.getLeft() != null) {
                //找到current的左子树上的最右节点
                TreeNode mostRight = current.getLeft();
                while (mostRight.getRight() != null && mostRight.getRight() != current) {
                    mostRight = mostRight.getRight();
                }
                //如果current的左子树的最右节点的右指针为空.将其指向当前节点
                if (mostRight.getRight() == null) {
                    mostRight.setRight(current);
                    current = current.getLeft();
                    continue;
                } else {
                    // 如果当前节点的左子树的最右节点的右指针指向current 表明这是第二次来到current了，
                    mostRight.setRight(null);
                    System.out.printf(current.getVal() + "");//中序遍历
                }
            } else {
                System.out.printf(current.getVal() + "");//中序遍历  需要考虑左子树为空的情况
            }
            current = current.getRight();
        }

    }
}
